/*
 * @lc app=leetcode.cn id=84 lang=javascript
 *
 * [84] 柱状图中最大的矩形
 */

// @lc code=start
/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  let stack = [];
  let max = 0;

  let preMin = new Array(heights.length).fill(-1);
  let nextMin = new Array(heights.length).fill(heights.length);

  // 高度为heights[i]时的最大面积
  // 查找前后小于当前柱子的柱子
  for (let i = 0; i < heights.length; i++) {
    while(stack.length && heights[i] < heights[stack[stack.length - 1]]){
      nextMin[stack.pop()] = i;
    }
    if(stack.length){
      preMin[i] = stack[stack.length - 1];
    }
    stack.push(i);
  }

  for (let i = 0; i < heights.length; i++) {
    let s = Math.abs((nextMin[i] - preMin[i] - 1) * heights[i]);
    max = Math.max(max, s);
  }
  return max;

};
// @lc code=end

